{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Strings Differ by One Character"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: differByOne"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #只有一个不同字符的字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串列表&nbsp;<code>dict</code> ，其中所有字符串的长度都相同。</p>\n",
    "\n",
    "<p>当存在两个字符串在相同索引处只有一个字符不同时，返回 <code>True</code> ，否则返回 <code>False</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dict = [\"abcd\",\"acbd\", \"aacd\"]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>字符串 \"a<strong>b</strong>cd\" 和 \"a<strong>a</strong>cd\" 只在索引 1 处有一个不同的字符。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dict = [\"ab\",\"cd\",\"yz\"]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dict = [\"abcd\",\"cccc\",\"abyd\",\"abab\"]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>dict</code>&nbsp;中的字符数小于或等于&nbsp;<code>10^5</code>&nbsp;。</li>\n",
    "\t<li><code>dict[i].length == dict[j].length</code></li>\n",
    "\t<li><code>dict[i]</code>&nbsp;是互不相同的。</li>\n",
    "\t<li><code>dict[i]</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以以 <code>O(n*m)</code> 的复杂度解决问题吗？其中 n 是列表 <code>dict</code> 的长度，<code>m</code> 是字符串的长度。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [strings-differ-by-one-character](https://leetcode.cn/problems/strings-differ-by-one-character/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [strings-differ-by-one-character](https://leetcode.cn/problems/strings-differ-by-one-character/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"abcd\",\"acbd\", \"aacd\"]', '[\"ab\",\"cd\",\"yz\"]', '[\"abcd\",\"cccc\",\"abyd\",\"abab\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dict: List[str]) -> bool:\n",
    "        for i in range(len(dict[0])):\n",
    "            if len(set(map(lambda x: x[:i]+x[i+1:], dict))) != len(dict):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dict: List[str]) -> bool:\n",
    "        dict_list = dict\n",
    "        str_len = len(dict_list[0])\n",
    "        dict_len = len(dict_list)\n",
    "        for index in range(str_len):\n",
    "            if len(set(map(lambda x: x[:index] + x[index + 1:], dict_list))) != dict_len:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dict_list: List[str]) -> bool:\n",
    "        str_len = len(dict_list[0])\n",
    "        dict_len = len(dict_list)\n",
    "        for index in range(str_len):\n",
    "            if len(set(map(lambda x: x[:index] + x[index + 1:], dict_list))) != dict_len:\n",
    "                return True\n",
    "        return False\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 哈希统计 模式频率\n",
    "    # 1.每个字符串，每个位置换成“*”，作为一种模式mode\n",
    "    # 2.统计每个模式mode的频率\n",
    "    # 3.因为word互不相同，所以只要同一模式，出现了2次，那就是有符合条件的\n",
    "    # 4.若题目说，可能word会相同，则用个set来统计，看set中是否有2个\n",
    "    def differByOne(self, dict: List[str]) -> bool:\n",
    "        \n",
    "\n",
    "        n = len(dict[0])\n",
    "        for i in range(n):\n",
    "            mode_freq = defaultdict(int)    #题目说，单词互不相同，所以只统计频率。否则要存储具体的单词，比较一下\n",
    "            for word in dict:\n",
    "                mode = word[ :i] + '*' + word[i+1: ]\n",
    "                mode_freq[mode] += 1\n",
    "                if mode_freq[mode] == 2:    #给的数据，单词互不相同。所以就不用再判断两词是否不同了\n",
    "                    return True\n",
    "\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, words: List[str]) -> bool:\n",
    "        mod = 1_000_000_007 # prime\n",
    "        \n",
    "        # might have hash collisions here, so store mapping of hash -> list of words\n",
    "        hashes = defaultdict(list) \n",
    "        for w in words:\n",
    "            hashes[self.getHash(mod, w)].append(w)\n",
    "                \n",
    "        for w in words:\n",
    "            origHash = self.getHash(mod, w)\n",
    "            mult = 1\n",
    "            \n",
    "            for i, c in enumerate(w):\n",
    "                hashWithoutC = (origHash - mult * self.ord(c)) % mod\n",
    "                \n",
    "                for newc in [notc for notc in ascii_lowercase if notc != c]:\n",
    "                    newHash = (hashWithoutC + (mult * self.ord(newc))) % mod\n",
    "                \n",
    "                    if newHash in hashes:\n",
    "\t\t\t\t\t\t# check if actual match or just hash collision\n",
    "                        newStr = w[:i] + newc + w[i + 1:]\n",
    "                        if any(newStr == s for s in hashes[newHash]):\n",
    "                            return True\n",
    "            \n",
    "                mult = (mult * 26) % mod\n",
    "            \n",
    "        return False\n",
    "            \n",
    "        \n",
    "    def getHash(self, mod, w):\n",
    "        h = 0\n",
    "        mult = 1\n",
    "        \n",
    "        for c in w:\n",
    "            h = (h + mult * self.ord(c)) % mod\n",
    "            mult = (mult * 26) % mod\n",
    "        \n",
    "        return h\n",
    "    \n",
    "    def ord(self, c):\n",
    "        return ord(c) - ord('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, words: List[str]) -> bool:\n",
    "        mod = 1_000_000_007 # prime\n",
    "        # might have hash collisions here, so store mapping of hash -> list of words\n",
    "        hashes = collections.defaultdict(list) \n",
    "        for w in words:\n",
    "            hashes[self.getHash(mod, w)].append(w)\n",
    "        for w in words:\n",
    "            origHash = self.getHash(mod, w)\n",
    "            mult = 1\n",
    "            for i, c in enumerate(w):\n",
    "                hashWithoutC = (origHash - mult * self.ord(c)) % mod\n",
    "                for newc in [notc for notc in string.ascii_lowercase if notc != c]:\n",
    "                    newHash = (hashWithoutC + mult * self.ord(newc)) % mod\n",
    "                    if newHash in hashes:\n",
    "\t\t\t\t\t\t# check if actual match or just hash collision\n",
    "                        newStr = w[:i] + newc + w[i + 1:]\n",
    "                        if any(newStr == s for s in hashes[newHash]):\n",
    "                            return True\n",
    "                mult = (mult * 26) % mod\n",
    "        return False\n",
    "            \n",
    "    def getHash(self, mod, w):\n",
    "        h = 0\n",
    "        mult = 1\n",
    "        for c in w:\n",
    "            h = (h + mult * self.ord(c)) % mod\n",
    "            mult = (mult * 26) % mod\n",
    "        return h\n",
    "    \n",
    "    def ord(self, c):\n",
    "        return ord(c) - ord('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, words: List[str]) -> bool:\n",
    "        mod = 1_000_000_007 # prime\n",
    "        # might have hash collisions here, so store mapping of hash -> list of words\n",
    "        hashes = collections.defaultdict(list) \n",
    "        for w in words:\n",
    "            hashes[self.getHash(mod, w)].append(w)\n",
    "        for w in words:\n",
    "            origHash = self.getHash(mod, w)\n",
    "            mult = 1\n",
    "            for i, c in enumerate(w):\n",
    "                hashWithoutC = (origHash - mult * self.ord(c)) % mod\n",
    "                for newc in [notc for notc in string.ascii_lowercase if notc != c]:\n",
    "                    newHash = (hashWithoutC + (mult * self.ord(newc))) % mod\n",
    "                    if newHash in hashes:\n",
    "\t\t\t\t\t\t# check if actual match or just hash collision\n",
    "                        newStr = w[:i] + newc + w[i + 1:]\n",
    "                        if any(newStr == s for s in hashes[newHash]):\n",
    "                            return True\n",
    "                mult = (mult * 26) % mod\n",
    "        return False\n",
    "            \n",
    "    def getHash(self, mod, w):\n",
    "        h = 0\n",
    "        mult = 1\n",
    "        for c in w:\n",
    "            h = (h + mult * self.ord(c)) % mod\n",
    "            mult = (mult * 26) % mod\n",
    "        return h\n",
    "    \n",
    "    def ord(self, c):\n",
    "        return ord(c) - ord('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dict: List[str]) -> bool:\n",
    "        if len(dict) == 1:\n",
    "            return False\n",
    "        ln = len(dict[0])\n",
    "        if ln == 1:\n",
    "            cnt = Counter(dict)\n",
    "            return len(cnt) > 1\n",
    "        mid = ln // 2\n",
    "        que = defaultdict(list)\n",
    "        for word in dict:\n",
    "            que[word[:mid]].append(word[mid:])\n",
    "        for k, v in que.items():\n",
    "            if self.differByOne(v):\n",
    "                return True \n",
    "        d = defaultdict(list)\n",
    "        for word in dict:\n",
    "            d[word[mid:]].append(word[:mid])\n",
    "        for k, v in d.items():\n",
    "            if self.differByOne(v):\n",
    "                return True \n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dict: List[str]) -> bool:\n",
    "        def dfs(s):\n",
    "            l = 0\n",
    "            r = len(s[0])-1\n",
    "            if l<r:\n",
    "                top_half = defaultdict(list)\n",
    "                bottom_half = defaultdict(list)\n",
    "                m = (l+r+1) // 2\n",
    "                for w in s:\n",
    "                    top = w[:m]\n",
    "                    bottom = w[m:]\n",
    "                    top_half[top].append(bottom)\n",
    "                    bottom_half[bottom].append(top)\n",
    "                for _,v in top_half.items():\n",
    "                    if len(v)>1 and dfs(v):\n",
    "                        return True\n",
    "                for _,v in bottom_half.items():\n",
    "                    if len(v)>1 and dfs(v):\n",
    "                        return True\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        return dfs(dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dict: List[str]) -> bool:\n",
    "        base,mod = 27,10**18+3\n",
    "        n = len(dict[0])\n",
    "        has = set()\n",
    "        for s in dict:\n",
    "            ss = [ord(x)-ord('a')+1 for x in s]#把字符串都转成数字来进行字符串哈希，+1是为了留空\n",
    "            pre = 0\n",
    "            for i in ss: pre = (pre*base+i)%mod\n",
    "            hou = 1\n",
    "            for i in range(n-1,-1,-1):#枚举所有可以留空的位置\n",
    "                lin = (pre-hou*ss[i])%mod\n",
    "                if lin in has:return True\n",
    "                has.add(lin)\n",
    "                hou = (hou*base)%mod\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dict: List[str]) -> bool:\n",
    "        base,mod = 27,10**18+3\n",
    "        n = len(dict[0])\n",
    "        has = set()\n",
    "        for s in dict:\n",
    "            ss = [ord(x)-ord('a')+1 for x in s]#把字符串都转成数字来进行字符串哈希，+1是为了留空\n",
    "            pre = 0\n",
    "            for i in ss: pre = (pre*base+i)%mod\n",
    "            hou = 1\n",
    "            for i in range(n-1,-1,-1):#枚举所有可以留空的位置\n",
    "                lin = (pre-hou*ss[i])%mod\n",
    "                if lin in has:return True\n",
    "                has.add(lin)\n",
    "                hou = (hou*base)%mod\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dict: List[str]) -> bool:\n",
    "        base,mod = 27,10**18+3\n",
    "        n = len(dict[0])\n",
    "        has = set()\n",
    "        for s in dict:\n",
    "            ss = [ord(x)-ord('a')+1 for x in s]#把字符串都转成数字来进行字符串哈希，+1是为了留空\n",
    "            pre = 0\n",
    "            for i in ss: pre = (pre*base+i)%mod\n",
    "            hou = 1\n",
    "            for i in range(n-1,-1,-1):#枚举所有可以留空的位置\n",
    "                lin = (pre-hou*ss[i])%mod\n",
    "                if lin in has:return True\n",
    "                has.add(lin)\n",
    "                hou = (hou*base)%mod\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dict: List[str]) -> bool:\n",
    "        base,mod = 27,10**18+3\n",
    "        n = len(dict[0])\n",
    "        has = set()\n",
    "        for s in dict:\n",
    "            ss = [ord(x)-ord('a')+1 for x in s]#把字符串都转成数字来进行字符串哈希，+1是为了留空\n",
    "            pre = 0\n",
    "            for i in ss: pre = (pre*base+i)%mod\n",
    "            hou = 1\n",
    "            for i in range(n-1,-1,-1):#枚举所有可以留空的位置\n",
    "                lin = (pre-hou*ss[i])%mod\n",
    "                if lin in has:return True\n",
    "                has.add(lin)\n",
    "                hou = (hou*base)%mod\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dict: List[str]) -> bool:\n",
    "        base,mod = 27,10**18+3\n",
    "        n = len(dict[0])\n",
    "        has = set()\n",
    "        for s in dict:\n",
    "            ss = [ord(x)-ord('a')+1 for x in s]#把字符串都转成数字来进行字符串哈希，+1是为了留空\n",
    "            pre = 0\n",
    "            for i in ss: pre = (pre*base+i)%mod\n",
    "            hou = 1\n",
    "            for i in range(n-1,-1,-1):#枚举所有可以留空的位置\n",
    "                lin = (pre-hou*ss[i])%mod\n",
    "                if lin in has:return True\n",
    "                has.add(lin)\n",
    "                hou = (hou*base)%mod\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mx = 10 ** 5\n",
    "mod = 10 ** 18 + 3\n",
    "mul = [1] * mx \n",
    "for i in range(1, mx):\n",
    "    mul[i] = (mul[i - 1] * 31) % mod \n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dict: List[str]) -> bool:\n",
    "        n = len(dict[0])\n",
    "\n",
    "        def f(x):\n",
    "            tmp = 0\n",
    "            for ch in x:\n",
    "                tmp = (tmp * 31 + (ord(ch) - ord('a'))) % mod \n",
    "            return tmp \n",
    "        \n",
    "        res = set()\n",
    "        for word in dict:\n",
    "            base = f(word)\n",
    "            for i in range(n):\n",
    "                tmp = (base + (27 - ord(word[i]) + ord('a')) * mul[n - i - 1]) % mod \n",
    "                if tmp in res:\n",
    "                    return True \n",
    "                res.add(tmp)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mx = 10 ** 5\n",
    "mod = 10 ** 9 + 7\n",
    "mod1 = 10 ** 9 + 21\n",
    "mul = [1] * mx \n",
    "mul1 = [1] * mx \n",
    "for i in range(1, mx):\n",
    "    mul[i] = (mul[i - 1] * 31) % mod \n",
    "    mul1[i] = (mul1[i - 1] * 31) % mod1 \n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dict: List[str]) -> bool:\n",
    "        n = len(dict[0])\n",
    "\n",
    "        def f(x):\n",
    "            tmp = 0\n",
    "            for ch in x:\n",
    "                tmp = (tmp * 31 + (ord(ch) - ord('a'))) % mod \n",
    "            return tmp \n",
    "        \n",
    "        def g(x):\n",
    "            tmp = 0\n",
    "            for ch in x:\n",
    "                tmp = (tmp * 31 + (ord(ch) - ord('a'))) % mod1 \n",
    "            return tmp \n",
    "\n",
    "        res = set()\n",
    "        res1 = set()\n",
    "        for word in dict:\n",
    "            base = f(word)\n",
    "            base1 = g(word)\n",
    "            for i in range(n):\n",
    "                tmp = (base + (27 - ord(word[i]) + ord('a')) * mul[n - i - 1]) % mod \n",
    "                tmp1 = (base1 + (27 - ord(word[i]) + ord('a')) * mul1[n - i - 1]) % mod1 \n",
    "                if tmp in res and tmp1 in res1:\n",
    "                    return True \n",
    "                res.add(tmp)\n",
    "                res1.add(tmp1)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "_MOD = 1000000007\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dct: List[str]) -> bool:\n",
    "        m = len(dct[0])\n",
    "        p = [1]\n",
    "        for i in range(m - 1):\n",
    "            p.append((p[-1] * 27) % _MOD)\n",
    "        table = defaultdict(list)\n",
    "        for i, w in enumerate(dct):\n",
    "            h = 0\n",
    "            for j, c in enumerate(w):\n",
    "                h = (h + (ord(c) - ord('a') + 1) * p[j]) % _MOD\n",
    "            for j, c in enumerate(w):\n",
    "                h_rem = (h - (ord(c) - ord('a') + 1) * p[j] + _MOD) % _MOD\n",
    "                if h_rem in table:\n",
    "                    for i_p, j_p in table[h_rem]:\n",
    "                        if i == i_p or j != j_p:\n",
    "                            continue\n",
    "                        if all(dct[i_p][k] == w[k] if k != j else dct[i_p][k] != w[k] for k in range(m)):\n",
    "                            return True \n",
    "                table[h_rem].append((i, j))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def differByOne(self, dict: List[str]) -> bool:\n",
    "        trie = Trie()\n",
    "        for w in dict:\n",
    "          if trie.query(w):\n",
    "            return True\n",
    "          trie.insert(w)\n",
    "        return False\n",
    "class Trie:\n",
    "  def __init__(self):\n",
    "    self.childs = defaultdict(Trie)\n",
    "  def insert(self, s):\n",
    "    cur = self\n",
    "    for c in s:\n",
    "      cur = cur.childs[c]\n",
    "  def query(self, s):\n",
    "    def dfs(trie, i, chance):\n",
    "      if i == len(s):\n",
    "        return chance == 0\n",
    "      if s[i] in trie.childs:\n",
    "        if dfs(trie.childs[s[i]], i + 1, chance):\n",
    "          return True\n",
    "      if chance == 0:\n",
    "        return False\n",
    "      for c in  trie.childs:\n",
    "        if dfs(trie.childs[c], i + 1, chance - 1):\n",
    "          return True\n",
    "      return False\n",
    "    return dfs(self, 0, 1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
